//n 位格雷码序列 是一个由 2ⁿ 个整数组成的序列，其中：
//
// 
// 每个整数都在范围 [0, 2ⁿ - 1] 内（含 0 和 2ⁿ - 1） 
// 第一个整数是 0 
// 一个整数在序列中出现 不超过一次 
// 每对 相邻 整数的二进制表示 恰好一位不同 ，且 
// 第一个 和 最后一个 整数的二进制表示 恰好一位不同 
// 
//
// 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 2
//输出：[0,1,3,2]
//解释：
//[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
//- 00 和 01 有一位不同
//- 01 和 11 有一位不同
//- 11 和 10 有一位不同
//- 10 和 00 有一位不同
//[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
//- 00 和 10 有一位不同
//- 10 和 11 有一位不同
//- 11 和 01 有一位不同
//- 01 和 00 有一位不同
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[0,1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 16 
// 
//
// Related Topics 位运算 数学 回溯 👍 709 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-09-23 00:25:51
 * @description 89.格雷编码
 */
public class GrayCode{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 GrayCode fun=new GrayCode();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //000 001 011 010 110 111 101 100
    public List<Integer> grayCode1(int n) {
		java.util.List<Integer> result = new java.util.ArrayList<>();
		int total = 1 << n; // 2^n
		for (int i = 0; i < total; i++) {
			// 生成格雷码的公式：i ^ (i >> 1)
			result.add(i ^ (i >> 1));
		}
		return result;
    }
	// 时间复杂度：O(2^n)，需要生成 2^n 个格雷码。
	public List<Integer> grayCode2(int n) {
		List<Integer> result = new java.util.ArrayList<>();
		result.add(0); // 初始格雷码序列包含 0
		for (int i = 0; i < n; i++) {
			int size = result.size();
			int prefix = 1 << i; // 当前位的前缀值
			// 反向遍历现有的格雷码序列，并在每个元素前添加前缀
			for (int j = size - 1; j >= 0; j--) {
				result.add(prefix + result.get(j));
			}
		}
		return result;
	}
	public List<Integer> grayCode(int n) {
		List<Integer> result = new ArrayList<>();
		boolean[] visited = new boolean[1 << n];

		// 从0开始
		result.add(0);
		visited[0] = true;

		backtrack(result, visited, n);
		return result;
	}

	private boolean backtrack(List<Integer> result, boolean[] visited, int n) {
		if (result.size() == (1 << n)) {
			// 检查首尾是否也只有一位不同（循环格雷码）
			int first = result.get(0);
			int last = result.get(result.size() - 1);
			int diff = first ^ last;
			return (diff & (diff - 1)) == 0;  // 检查是否只有一位不同
		}

		int current = result.get(result.size() - 1);

		for (int i = 0; i < n; i++) {
			int next = current ^ (1 << i);
			if (!visited[next]) {
				visited[next] = true;
				result.add(next);

				if (backtrack(result, visited, n)) {
					return true;
				}

				// 回溯
				visited[next] = false;
				result.remove(result.size() - 1);
			}
		}
		return false;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
